package com.cn.codebrush.栈;

import java.util.Deque;
import java.util.LinkedList;

public class No735行星碰撞 {
    public static void main(String[] args) {
        int[] temperatures = {-2,1,1,-1};
        System.out.println(asteroidCollision(temperatures));
    }

    /**
     * [-2,-1,1,2]
     * [-2,-2,1,-2]
     * [-2,-2,1,-1]
     * [-2,1,1,-1]
     * 输入：asteroids = [5,10,-5]   [10,2,-5]
     * 输出：[5,10]
     * 解释：10 和 -5 碰撞后只剩下 10 。 5 和 10 永远不会发生碰撞。

     * @param asteroids
     * @return
     */
    public static int[] asteroidCollision(int[] asteroids) {
        int n = asteroids.length;
        Deque<Integer> deque = new LinkedList<>();
        for(int i=0;i<n;i++){
            boolean flag = true;
            while (flag && !deque.isEmpty() && deque.peek()>0 && asteroids[i]<0){
               flag = Math.abs(deque.peek())<Math.abs(asteroids[i]);
                if(Math.abs(deque.peek())<=Math.abs(asteroids[i])){
                    deque.poll();
                }else {
                    break;
                }
            }

            if(flag){
                deque.push(asteroids[i]);
            }
        }

        int[] res = new int[deque.size()];
        int j = 0;
        while (!deque.isEmpty()){
            res[j++] = deque.pollLast();
        }

        return res;
    }
}
